package puzzle.sudoku.solver;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import puzzle.common.data.HatanException;
import puzzle.common.point.Pnt;
import puzzle.common.solver.AbstractSolver;
import puzzle.common.solver.AbstractTopology;
import puzzle.common.solver.BoardSnapshot;
import puzzle.common.solver.SolutionState;
import puzzle.sudoku.data.SudokuBoard;
import tomoto.util.FastBitSet;

public class SudokuSolver extends AbstractSolver<SudokuBoard, AbstractTopology, SudokuAssumption> {

	public SudokuSolver() {
		addRule(new NumberPossibilityRule());
	}

	@Override
	protected AbstractTopology analyzeTopology(SudokuBoard b) {
		return null;
	}

	@Override
	protected SolutionState checkSolutionState(SudokuBoard b, AbstractTopology topology) {
		return b.getNumOfFixedCells() == b.width * b.height ? SolutionState.COMPLETE
				: SolutionState.INCOMPLETE;
	}

	@Override
	protected List<SudokuAssumption> assume(SudokuBoard b, AbstractTopology topology,
			SudokuAssumption prevAssumption) {
		List<PntEntry> entries = new ArrayList<PntEntry>();
		
		for (int y = 0; y < b.height; y++) {
			for (int x = 0; x < b.width; x++) {
				if (b.getNumber(x, y) == 0) {
					FastBitSet f = b.getForbiddenFlags(x, y);
					PntEntry entry = new PntEntry(x, y, f);
					entries.add(entry);
				}
			}
		}
		
		Collections.sort(entries);
		
		List<SudokuAssumption> result = new ArrayList<SudokuAssumption>();
		for (PntEntry entry : entries) {
			for (int n : entry.numbers) {
				result.add(new SudokuAssumption(entry.p, n));
			}
		}
		
		return result;
	}

	public class PntEntry implements Comparable<PntEntry> {

		public final Pnt p;
		public final int[] numbers;
		
		public PntEntry(int x, int y, FastBitSet f) {
			p = new Pnt(x, y);
			numbers = new int[f.size() - f.countBits()];
			int n = -1;
			int i = 0;
			while (true) {
				n = f.find(false, n + 1);
				if (n == -1) break;
				numbers[i++] = n + 1;
			}
		}

		public int compareTo(PntEntry other) {
			return other.numbers.length - this.numbers.length;
		}

	}

	@Override
	protected void applyAssumption(
			List<BoardSnapshot<SudokuBoard, AbstractTopology, SudokuAssumption>> bss,
			SudokuBoard b, SudokuAssumption a) throws HatanException {
		b.setNumber(a.p.x, a.p.y, a.n);
		b.setAssumed(a.p.x, a.p.y);
	}

	@Override
	protected void excludeAssumption(SudokuBoard b, SudokuAssumption a) throws HatanException {
		b.forbidNumber(a.p.x, a.p.y, a.n);
	}

	@Override
	protected boolean isAlreadyTried(
			List<BoardSnapshot<SudokuBoard, AbstractTopology, SudokuAssumption>> bss,
			SudokuBoard b, SudokuAssumption a) {
		if (b.getNumber(a.p.x, a.p.y) != 0) {
			return true;
		}

		for (BoardSnapshot<SudokuBoard, AbstractTopology, SudokuAssumption> bs : bss) {
			if (bs.getBoard().getNumber(a.p.x, a.p.y) == a.n) {
				return true;
			}
		}

		return false;
	}

	@Override
	protected void sortBoardSnapshots(
			List<BoardSnapshot<SudokuBoard, AbstractTopology, SudokuAssumption>> bss) {
		Collections.sort(bss, COMPARATOR);
	}

	private static final Comparator<BoardSnapshot<SudokuBoard, AbstractTopology, SudokuAssumption>> COMPARATOR = new Comparator<BoardSnapshot<SudokuBoard, AbstractTopology, SudokuAssumption>>() {
		public int compare(BoardSnapshot<SudokuBoard, AbstractTopology, SudokuAssumption> o1,
				BoardSnapshot<SudokuBoard, AbstractTopology, SudokuAssumption> o2) {
			return o2.getBoard().getNumOfFixedCells() - o1.getBoard().getNumOfFixedCells();
		}

	};

}
